A bus architecture of a computer system conveys much of the information and signals involved in the computer system's operation. In a typical computer system, one or more busses are used to connect a central processing unit (CPU) to a memory and to input/output elements so that data and control signals can be readily transmitted between these different components. When the computer system executes its programming, it is imperative that data and information flow as fast as possible in order to make the computer as responsive as possible to the user and to efficiently execute its assigned tasks. With many peripheral devices, such as graphics adapters, full motion video adapters, small computer systems interface (SCSI) host bus adapters, and the like, it is imperative that large block data transfers be accomplished expeditiously for efficient execution. These devices are just some examples of subsystems which benefit substantially from a very fast bus transfer rate.
Much of a computer system's functionality and usefulness to a user is derived from the functionality of the peripheral devices. For example, the speed and responsiveness of the graphics adapter is a major factor in a computer system's usefulness as an entertainment device. Or, for example, the speed with which video files can be retrieved from a hard drive and played by the graphics adapter determines the computer system's usefulness as a training aid. Hence, the rate at which data can be transferred among the various peripheral devices often determines whether the computer system is suited for a particular purpose. The electronics industry has, over time, developed several types of bus architectures. Recently, the PCI (peripheral component interconnect) bus architecture has become one of the most widely used, widely supported bus architectures. The PCI bus was developed to provide a high speed, low latency bus architecture from which a large variety of systems could be developed.
Prior Art FIG. 1 shows a typical PCI bus architecture 100. PCI bus architecture 100 is comprised of a CPU 102 and a main memory 104, coupled to a host PCI bridge containing arbiter 106 (hereafter arbiter 106) through a CPU local bus 108 and memory bus 110, respectively. A PCI bus 112 is coupled to each of PCI agents 114, 116, 118, 120, 122, 124 respectively, and is coupled to arbiter 106.
Referring still to Prior Art FIG. 1, each of PCI agents 114, 116, 118, 120, 122, 124 (hereafter, PCI agents 114-124) residing on PCI bus 112 use PCI bus 112 to transmit and receive data. PCI bus 112 is comprised of functional signal lines, for example, interface control lines, address/data lines, error signal lines, and the like. Each of PCI agents 114-124 are coupled to the functional signal lines comprising PCI bus 112. When one of PCI agents 114-124 requires the use of PCI bus 112 to execute a data transaction, it requests PCI bus ownership from arbiter 106. The PCI agent requesting ownership is referred to as an "initiator", or bus master. Upon being granted ownership of PCI bus 112 from arbiter 106, the initiator (e.g., PCI agent 116) carries out its respective data transaction (e.g., transfer a file).
Each of PCI agents 114-124 may independently request PCI bus ownership. Thus, at any given time, several of PCI agents 114-124 may be requesting PCI bus ownership simultaneously. Where there are simultaneous requests for PCI bus ownership, arbiter 106 arbitrates between requesting PCI agents, determining which requesting PCI agent is granted PCI bus ownership. When one of PCI agents 114-124 is granted PCI bus ownership, it initiates its transaction (e.g., file transfer) with a "target" or slave device (e.g., main memory 104). When the data transaction is complete, the PCI agent relinquishes ownership of PCI bus 112, allowing arbiter 106 to reassign PCI bus 112 to another requesting PCI agent.
Thus, only one data transaction can take place on a PCI bus at any given time. In order to maximize the efficiency and data transfer bandwidth of PCI bus 112, PCI agents 114-124 follow a definitive set of protocols. These protocols are designed to standardize the method of accessing, utilizing, and relinquishing PCI bus 112, so as to maximize its data transfer bandwidth while ensuring interoperability among various PCI bus devices from various manufacturers. The PCI bus protocols and specifications are set forth in an industry standard PCI specification (e.g., PCI Specification--Revision 2.1). Where each of PCI agents 114-124 are high performance, well designed devices, data transfer rates approaching 528 Mbytes per second can be achieved (e.g., a 64 bit PCI bus 112 operating at 66 MHz).
Sustaining consistently high data transfer rates across a PCI bus requires efficient allocation of PCI bus ownership, and thus, PCI bus bandwidth. Each device needs ownership of the PCI bus in accordance with its respective requirements. These requirements include, for example, latency tolerance, data transfer bandwidth, block transfer size, and the like. Some devices are more critical to the proper operation of the computer system than others. Some devices are less tolerant of latency than others. In addition, some devices need to transfer very large quantities of data. Hence, devices coupled to the PCI bus are of differing priority with regard to their respective requests for PCI bus ownership.
Efficiently managing the allocation of the PCI bus is essential to the proper operation of a computer system. Efficient allocation management assumes even greater importance when devices of differing priority require ownership of the PCI bus. As described above, only one device at a time can transfer data across the PCI bus. Consequently, competing devices arbitrate for ownership and the arbiter determines which device is granted the PCI bus. Afterwards, the remaining devices subsequently are forced to wait and continue arbitration. Some devices are more important to the functionality of the computer system than other devices and are thus considered high priority. Some devices are more tolerant of latency than other devices and are accordingly considered lower priority. The arbiter needs to ensure the bus is allocated among the competing devices, taking into account their relative priorities. To accomplish this, the arbiter follows a predetermined arbitration methodology, or arbitration scheme.
Prior Art FIG. 2 shows a typical prior art prioritized arbitration scheme 200. Arbitration scheme 200 shows the relative priority of 7 coupled devices, device 0 through device 6, where device 0 is the highest priority device and device 6 is the lowest priority device. Higher priority devices are allocated the higher priority positions in arbitration scheme 200 (e.g., device 0) while lower priority devices are allocated lower priority positions (e.g., device 6). For example, a network adapter card typically is required to transfer very large blocks of data from the network to main memory, which requires a disproportionately large amount of PCI bus data transfer bandwidth. The network adapter also typically has internal buffers of limited size, which cannot tolerate data transfer latency without incurring a buffer overrun or underrun. Consequently, the network adapter would be coupled as device 0. In contrast, a printer does not transfer particularly large blocks of data, is very tolerant of latency, and is thus coupled as device 6. In this manner, peripheral devices are coupled to the PCI bus and are granted ownership of the PCI bus according to their respective priorities. Hence, where all of devices 0 through 6 simultaneously request ownership, device 0 receives ownership first.
There is a problem, however, in that arbitration scheme 200 does not adequately match the differing requirements of bandwidth and priority of different devices. In arbitration scheme 200, where there are many high bandwidth devices using the PCI bus and where each issues successive requests for ownership, lower priority devices can be prevented from acquiring ownership for long periods of time, or "starved" of PCI bus bandwidth. Arbitration scheme 200 does not ensure low priority devices are not prevented from acquiring ownership.
For example, at any time device 6 and any other device request ownership, device 6 "loses" the arbitration and is required to wait for a successive arbitration following the resulting data transaction. Where there are numerous requests for access from other devices, each one of which is of a higher priority than device 6, there may be very prolonged periods of time during which device 6 never aquires ownership. To ensure proper operation of the computer system, higher priority devices, which typically require large amounts of data transfer bandwidth, occupy the higher priority positions. While this assists the higher priority devices in receiving their required data transfer bandwidth, low priority devices can be easily starved.
Thus, what is required is an arbitration scheme which is much more flexible with regard to allocating PCI bus bandwidth. The required solution needs to ensure low priority devices are not starved while ensuring high priority devices are adequately served. The required system needs to efficiently allocate PCI bus bandwidth to maximize the overall functionality of a computer system. The present invention provides a novel solution to the above requirements.